package point;

import java.util.ArrayList;

/**
 * 题目： 和为 S 的连续正数序列
 * 输出所有和为 S 的连续正数序列。例如和为 100 的连续序列有：
 * [9, 10, 11, 12, 13, 14, 15, 16]
 * [18, 19, 20, 21, 22]
 *
 * @Author Gavin
 * @date 2022.08.06 16:45
 */
public class sum_3 {
    public ArrayList<ArrayList<Integer>> solution(int sum) {
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        int start = 1, end = 2;
        int curSum = 3;
        /**
         * 临界值：
         * 只要end的值小于sum就行
         */
        while (end < sum) {
            //因为是连续序列（递增的特点），如果curSum>sum说明连续子序列加起来的总和就大于sum了，这时候左指针需要向右移动一位
            if (curSum > sum) {
                curSum -= start;
                start++;
            } else if (curSum < sum) {//和上面情况相反，子序列总和小于的话右指针就需要右移动一位
                end++;
                curSum += end;
            } else {
                ArrayList<Integer> list = new ArrayList<>();
                for (int i = start; i <= end; i++)
                    list.add(i);
                ret.add(list);
                curSum -= start;
                start++;//左指针右移动一位
                end++;//右指针也右移动一位
                curSum += end;
            }
        }
        return ret;
    }

    /**
     *这种方式性能不是很好,但是容易理解
     */
    public static ArrayList<ArrayList<Integer>> solution_2(int sum) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if (sum <= 1) {
            ArrayList<Integer> pre = new ArrayList<>();
            pre.add(sum);
            result.add(pre);
            return result;
        }
        for (int i = 1; i < sum - 1; i++) {
            int preSum = i;
            ArrayList<Integer> pre = new ArrayList<>();
            pre.add(i);
            for (int j = i + 1; j < sum - 1; j++) {
                pre.add(j);
                preSum = preSum + j;
                if (preSum == sum) {
                    result.add(pre);
                    break;
                }else if(preSum>sum){
                    break;
                }
            }
        }
        return result;
    }
}
